#include "pch.h"
#include "test_quadtree.hpp"




test_quadtree::test_quadtree()
   : m_seed(0)
{}
///////////////////////////////////////////////////////////////////////////////////////////////////




void test_quadtree::operator()()
{
   test_construction();
   test_insertion();
   test_filter();
}
///////////////////////////////////////////////////////////////////////////////////////////////////

void test_quadtree::test_construction()
{
   const uint8 maxDepth  = quadtree::defaultMaxDepth;
   const uint8 maxValues = quadtree::defaultMaxValues;
   const rectangle rect  = rectangle::center(0, 0, 2, 2);

   //
   // Test: Constructor #1
   //
   // Create a quadtree by specifying rectangle, maxDepth and maxValues.
   // Tests the number of elements, buckets, as well as the specified stuff
   // (ie. rectangle, max depth, etc...)
   //

   quadtree tree1(rect, maxDepth, maxValues);

   // An empty tree must have 0 elements, 1 bucket
   // and a depth of 0 after construction.
   ASSERT_EQUAL(0, tree1.numValues());
   ASSERT_EQUAL(1, tree1.numBuckets());
   ASSERT_EQUAL(0, tree1.depth());
   ASSERT_EQUAL(maxDepth, tree1.maxDepth());
   ASSERT_EQUAL(maxValues, tree1.maxValues());
   ASSERT_EQUAL(rect, tree1.rect());

   // However this function is required to return the direct
   // number of buckets, ie only the direct childs of the bucket
   // (which must be 0)
   ASSERT_EQUAL(0, tree1.bucketNumBuckets());


   //
   // Test: Constructor #2
   //
   // Construct a quadtree and immediately insert one element.
   // Tests that the tree actually contains one element.
   //

   quadtree tree2(rect, maxDepth, 20, value_type(rectangle::corners(0, 0, 0, 0), 1337));

   // When inserting one element, the tree should contain
   // exactly one element and store it in the root node
   // (It should never have to subdivide using this method)
   ASSERT_EQUAL(1, tree2.numBuckets());
   ASSERT_EQUAL(1, tree2.numValues());
   ASSERT_EQUAL(1, tree2.bucketNumValues());
   ASSERT_EQUAL(0, tree2.depth());


   //
   // Test: Using invalid parameters
   //
   // Specifying a maximum number of 0 values is illegal and should throw.
   //

   value_type values[10];

   ASSERT_THROWS(quadtree(rect, maxDepth, 0), boostext::programming_error);
   ASSERT_THROWS(quadtree(rect, maxDepth, 0, value_type(rectangle::corners(0, 0, 0, 0), 0)), boostext::programming_error);
   ASSERT_THROWS(quadtree(rect, maxDepth, 0, &values[0], &values[10]), boostext::programming_error);
}
///////////////////////////////////////////////////////////////////////////////////////////////////

void test_quadtree::test_insertion()
{
   const rectangle rect  = rectangle::center(0, 0, 20, 20);
   const uint8 maxDepth  = quadtree::defaultMaxDepth;
   const uint8 maxValues = 4;

   //
   // Test 1: Populate the tree manually
   //

   quadtree tree1(rect, maxDepth, maxValues);

   tree1.insert(value_type(rectangle::point(-5, -5), 0));
   tree1.insert(value_type(rectangle::point(5, -5), 1));
   tree1.insert(value_type(rectangle::point(-5, 5), 2));
   tree1.insert(value_type(rectangle::point(5, 5), 3));

   // Since the 
   ASSERT_EQUAL(1, tree1.numBuckets());
   ASSERT_EQUAL(4, tree1.numValues());

   tree1.insert(value_type(rectangle::point(0, 0), 4));
   tree1.insert(value_type(rectangle::point(1, 1), 5));

   // We've inserted values which should have caused the tree
   // to split itself up (1 root bucket + 4 child buckets)
   // Thus the depth should be 1 and there should be 5 buckets
   // and 6 elements in total  (and the root bucket is empty)
   ASSERT_EQUAL(1, tree1.depth());
   ASSERT_EQUAL(5, tree1.numBuckets());
   ASSERT_EQUAL(6, tree1.numValues());
   ASSERT_EQUAL(0, tree1.bucketNumValues());


   //
   // Test 2: Populate the tree in a random fashion
   //
   // Creates a set with exactly the same values and then iterates over
   // the set and searches each value in the quadtree.
   //

   const std::size_t numElements = 1000;

   quadtree tree2(rect);
   set      set2;

   fill(tree2, numElements);
   fill(set2,  tree2);

   ASSERT_EQUAL(numElements, tree2.size());
   ASSERT_EQUAL(numElements, tree2.numValues());

   foreach(const value_type& value, set2)
   {
      iterator i = tree2.findExact(value.boundingRect());
      ASSERT(i != tree2.end());
      ASSERT(value == *i);
   }

	// Actually iterate over all buckets and test
	// if all values have been inserted into the right
	// bucket (the details are explained below).
	bucket_iterator it  = tree2.bucketBegin();
	bucket_iterator end = tree2.bucketEnd();
	while(it != end)
	{
		foreach(const value_type& value, *it)
		{
			rectangle iterRect = it.rect();
			rectangle bucketRect = it->rect();
			rectangle itemRect = boundingRect(value);
			ASSERT(iterRect == bucketRect);

			size2 bucketSize = it.rect().size();
			size2 itemSize   = itemRect.size();

			// An item is allowed to be inside a bucket if
			// -it's center is within the bucket's rectangle
			// -it's size is smaller or equal to the bucket's size
			// -(thus the item's rectangle is completely within the bucket's loose rectangle)
			ASSERT(it.rect().intersects(value.boundingRect().center()));
			ASSERT(itemSize.width <= bucketSize.width && itemSize.height <= bucketSize.height);

			ASSERT(it.looseRect().intersects(value.boundingRect()));
		}

		++it;
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////

void test_quadtree::test_filter()
{
	const rectangle rect = rectangle::center(0, 0, 20, 20);
	const std::size_t numValues = 1000;

	quadtree qtree(rect);
	set      stree;
	set      result;

	fill(qtree, numValues);

	std::size_t    seed = clock();
	rng            gen(seed);
	distribution   distribution_x(rect.left(), rect.right());
	distribution   distribution_y(rect.top(),  rect.bottom());
	die            die_x(gen, distribution_x);
	die            die_y(gen, distribution_y);

	for(std::size_t i = 0; i < 100; ++i)
	{
		rectangle   cull = rectangle::corners(die_x(), die_y(), die_x(), die_y()).normalized();

		// Do the culling by iterating over the entire tree manually, culling each element
		// and collecting the resulting values
		iterator it  = qtree.begin();
		iterator end = qtree.end();
		while(it != end)
		{
			if(cull.intersects(it->boundingRect()))
				result.insert(*it);

			++it;
		}

		// Now do the faster culling method that culls the buckets first
		// and cross-reference those results with the previously obtained results
		{
			rect_filter filter(cull);
			rect_filter::iterator it2 = qtree.begin(filter);
			rect_filter::iterator end = qtree.end(filter);

			while(it2 != end)
			{
				value_type value = *it2;

				if(cull.intersects(value.boundingRect()))
				{
					// NOT EVERY value that passes the test in this run
					// must have passed the test in the previous, naive
					// run, because values at the border of buckets are inserted
					// with preference into the upper/left ones, and not in
					// all they would intersect
					set::iterator f = result.find(value);

					if(f == result.end())
					{
						// Items at the border might have been inserted into another bucket
						continue;
					}

					ASSERT(value == *f);
					result.erase(f);
				}

				++it2;
			}
		}

		// After the culling pass, we should have found all results as we did in the previous pass
		// However if the previous pass revealed more values, then the second pass is wrong...
		std::size_t missed = result.size();
		ASSERT_EQUAL(0, missed);
		result.clear();
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////




void test_quadtree::fill(quadtree& tree, std::size_t numElements)
{
   rectangle rect = tree.rect();

   rng            gen(m_seed);
   distribution   distribution_x(rect.left(), rect.right());
   distribution   distribution_y(rect.top(),  rect.bottom());
   die            die_x(gen, distribution_x);
   die            die_y(gen, distribution_y);

   // Populate the tree
   for(std::size_t i = 0; i < numElements; ++i)
   {
      vector2 pos1(die_x(), die_y());
      vector2 pos2(die_x(), die_y());
      tree.insert(value_type(rectangle::corners(pos1, pos2).normalized(), i));
   }
}
///////////////////////////////////////////////////////////////////////////////////////////////////

void test_quadtree::fill(set& tree, const quadtree& qtree)
{
   const std::size_t numElements = qtree.size();
   const rectangle rect          = qtree.rect();

   rng            gen(m_seed);
   distribution   distribution_x(rect.left(), rect.right());
   distribution   distribution_y(rect.top(),  rect.bottom());
   die            die_x(gen, distribution_x);
   die            die_y(gen, distribution_y);

   for(std::size_t i = 0; i < numElements; ++i)
   {
      vector2 pos1(die_x(), die_y());
      vector2 pos2(die_x(), die_y());
      tree.insert(value_type(rectangle::corners(pos1, pos2).normalized(), i));
   }
}
///////////////////////////////////////////////////////////////////////////////////////////////////
